home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / ccs / ccs-11tl.lha / lbl / tifflib / tif_fax3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-20  |  28.5 KB  |  1,156 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/tiff/libtiff/RCS/tif_fax3.c,v 1.60 92/02/10 19:06:36 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1990, 1991, 1992 Sam Leffler
  7.  * Copyright (c) 1991, 1992 Silicon Graphics, Inc.
  8.  *
  9.  * Permission to use, copy, modify, distribute, and sell this software and 
  10.  * its documentation for any purpose is hereby granted without fee, provided
  11.  * that (i) the above copyright notices and this permission notice appear in
  12.  * all copies of the software and related documentation, and (ii) the names of
  13.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  14.  * publicity relating to the software without the specific, prior written
  15.  * permission of Sam Leffler and Silicon Graphics.
  16.  * 
  17.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  18.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  19.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  20.  * 
  21.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  22.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  23.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  24.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  25.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  26.  * OF THIS SOFTWARE.
  27.  */
  28.  
  29. /*
  30.  * TIFF Library.
  31.  *
  32.  * CCITT Group 3 and Group 4 Compression Support.
  33.  */
  34. #include "tiffioP.h"
  35. #include <stdio.h>
  36. #include <assert.h>
  37. #include "tif_fax3.h"
  38. #define    G3CODES
  39. #include "t4.h"
  40. #define    G3STATES
  41. #include "g3states.h"
  42.  
  43. typedef struct {
  44.     Fax3BaseState b;
  45. } Fax3DecodeState;
  46.  
  47. typedef struct {
  48.     Fax3BaseState b;
  49.     u_char    *wruns;
  50.     u_char    *bruns;
  51.     short    k;            /* #rows left that can be 2d encoded */
  52.     short    maxk;            /* max #rows that can be 2d encoded */
  53. } Fax3EncodeState;
  54.  
  55. #if USE_PROTOTYPES
  56. static    Fax3PreDecode(TIFF *);
  57. static    Fax3Decode(TIFF*, u_char *, int, u_int);
  58. static    int Fax3Decode1DRow(TIFF*, u_char *, int);
  59. static    Fax3PreEncode(TIFF *);
  60. static    Fax3PostEncode(TIFF *);
  61. static    Fax3Encode(TIFF*, u_char *, int, u_int);
  62. static    int Fax3Encode1DRow(TIFF *, u_char *, int);
  63. static    Fax3Close(TIFF *);
  64. static    Fax3Cleanup(TIFF *);
  65. static    void *Fax3SetupState(TIFF *, int);
  66. static    void fillspan(char *, int, int);
  67. static    int findspan(u_char **, int, int, u_char const *);
  68. static    int finddiff(u_char *, int, int, int);
  69. static    void skiptoeol(TIFF *, int);
  70. static    void putbits(TIFF *, u_int, u_int);
  71. static    void putcode(TIFF *, tableentry const *);
  72. static    void putspan(TIFF *, int, tableentry const *);
  73. extern    int TIFFFlushData1(TIFF *);
  74. #else
  75. static    int Fax3PreEncode(), Fax3Encode(), Fax3PostEncode();
  76. static    int Fax3Encode1DRow();
  77. static    int Fax3Decode(), Fax3PreDecode();
  78. static    int Fax3Decode1DRow();
  79. static    int Fax3Close(), Fax3Cleanup();
  80. static    void *Fax3SetupState();
  81. static    void fillspan();
  82. static    int findspan();
  83. static    int finddiff();
  84. static    void skiptoeol();
  85. static    void putbits();
  86. static    void putcode();
  87. static    void putspan();
  88. extern    int TIFFFlushData1();
  89. #endif
  90.  
  91. TIFFInitCCITTFax3(tif)
  92.     TIFF *tif;
  93. {
  94.     tif->tif_predecode = Fax3PreDecode;
  95.     tif->tif_decoderow = Fax3Decode;
  96.     tif->tif_decodestrip = Fax3Decode;
  97.     tif->tif_decodetile = Fax3Decode;
  98.     tif->tif_preencode = Fax3PreEncode;
  99.     tif->tif_postencode = Fax3PostEncode;
  100.     tif->tif_encoderow = Fax3Encode;
  101.     tif->tif_encodestrip = Fax3Encode;
  102.     tif->tif_encodetile = Fax3Encode;
  103.     tif->tif_close = Fax3Close;
  104.     tif->tif_cleanup = Fax3Cleanup;
  105.     tif->tif_options |= FAX3_CLASSF;    /* default */
  106.     tif->tif_flags |= TIFF_NOBITREV;    /* we handle bit reversal */
  107.     return (1);
  108. }
  109.  
  110. TIFFModeCCITTFax3(tif, isClassF)
  111.     TIFF *tif;
  112.     int isClassF;
  113. {
  114.     if (isClassF)
  115.         tif->tif_options |= FAX3_CLASSF;
  116.     else
  117.         tif->tif_options &= ~FAX3_CLASSF;
  118. }
  119.  
  120. static u_char bitMask[8] =
  121.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  122. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  123.  
  124. #define    is2DEncoding(tif) \
  125.     (tif->tif_dir.td_group3options & GROUP3OPT_2DENCODING)
  126. #define    fetchByte(tif, sp) \
  127.     ((tif)->tif_rawcc--, (sp)->b.bitmap[*(u_char *)(tif)->tif_rawcp++])
  128.  
  129. #define    BITCASE(b)            \
  130.     case b:                \
  131.     code <<= 1;            \
  132.     if (data & (1<<(7-b))) code |= 1;\
  133.     len++;                \
  134.     if (code > 0) { bit = b+1; break; }
  135.  
  136. /*
  137.  * Skip over input until an EOL code is found.  The
  138.  * value of len is passed as 0 except during error
  139.  * recovery when decoding 2D data.  Note also that
  140.  * we don't use the optimized state tables to locate
  141.  * an EOL because we can't assume much of anything
  142.  * about our state (e.g. bit position).
  143.  */
  144. static void
  145. skiptoeol(tif, len)
  146.     TIFF *tif;
  147.     int len;
  148. {
  149.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  150.     register int bit = sp->b.bit;
  151.     register int data = sp->b.data;
  152.     int code = 0;
  153.  
  154.     /*
  155.      * Our handling of ``bit'' is painful because
  156.      * the rest of the code does not maintain it as
  157.      * exactly the bit offset in the current data
  158.      * byte (bit == 0 means refill the data byte).
  159.      * Thus we have to be careful on entry and
  160.      * exit to insure that we maintain a value that's
  161.      * understandable elsewhere in the decoding logic.
  162.      */
  163.     if (bit == 0)            /* force refill */
  164.         bit = 8;
  165.     for (;;) {
  166.         switch (bit) {
  167.     again:    BITCASE(0);
  168.         BITCASE(1);
  169.         BITCASE(2);
  170.         BITCASE(3);
  171.         BITCASE(4);
  172.         BITCASE(5);
  173.         BITCASE(6);
  174.         BITCASE(7);
  175.         default:
  176.             if (tif->tif_rawcc <= 0)
  177.                 return;
  178.             data = fetchByte(tif, sp);
  179.             goto again;
  180.         }
  181.         if (len >= 12 && code == EOL)
  182.             break;
  183.         code = len = 0;
  184.     }
  185.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  186.     sp->b.data = data;
  187. }
  188.  
  189. /*
  190.  * Return the next bit in the input stream.  This is
  191.  * used to extract 2D tag values and the color tag
  192.  * at the end of a terminating uncompressed data code.
  193.  */
  194. static int
  195. nextbit(tif)
  196.     TIFF *tif;
  197. {
  198.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  199.     int bit;
  200.  
  201.     if (sp->b.bit == 0 && tif->tif_rawcc > 0)
  202.         sp->b.data = fetchByte(tif, sp);
  203.     bit = isBitSet(sp);
  204.     if (++(sp->b.bit) > 7)
  205.         sp->b.bit = 0;
  206.     return (bit);
  207. }
  208.  
  209. static void
  210. bset(cp, n, v)
  211.     register unsigned char *cp;
  212.     register int n;
  213.     register int v;
  214. {
  215.     while (n-- > 0)
  216.         *cp++ = v;
  217. }
  218.  
  219. /*
  220.  * Setup G3-related compression/decompression
  221.  * state before data is processed.  This routine
  222.  * is called once per image -- it sets up different
  223.  * state based on whether or not 2D encoding is used.
  224.  */
  225. static void *
  226. Fax3SetupState(tif, space)
  227.     TIFF *tif;
  228.     int space;
  229. {
  230.     TIFFDirectory *td = &tif->tif_dir;
  231.     Fax3BaseState *sp;
  232.     int cc = space;
  233.     long rowbytes, rowpixels;
  234.  
  235.     if (td->td_bitspersample != 1) {
  236.         TIFFError(tif->tif_name,
  237.             "Bits/sample must be 1 for Group 3/4 encoding/decoding");
  238.         return (0);
  239.     }
  240.     /*
  241.      * Calculate the scanline/tile widths.
  242.      */
  243.     if (isTiled(tif)) {
  244.         rowbytes = TIFFTileRowSize(tif);
  245.         rowpixels = tif->tif_dir.td_tilewidth;
  246.     } else {
  247.         rowbytes = TIFFScanlineSize(tif);
  248.         rowpixels = tif->tif_dir.td_imagewidth;
  249.     }
  250.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4)
  251.         cc += rowbytes+1;
  252.     tif->tif_data = malloc(cc);
  253.     if (tif->tif_data == NULL) {
  254.         TIFFError("Fax3SetupState",
  255.             "%s: No space for Fax3 state block", tif->tif_name);
  256.         return (0);
  257.     }
  258.     sp = (Fax3BaseState *)tif->tif_data;
  259.     sp->rowbytes = rowbytes;
  260.     sp->rowpixels = rowpixels;
  261.     sp->bitmap = (tif->tif_fillorder != td->td_fillorder ? 
  262.         TIFFBitRevTable : TIFFNoBitRevTable);
  263.     sp->white = (td->td_photometric == PHOTOMETRIC_MINISBLACK);
  264.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4) {
  265.         /*
  266.          * 2d encoding/decoding requires a scanline
  267.          * buffer for the ``reference line''; the
  268.          * scanline against which delta encoding
  269.          * is referenced.  The reference line must
  270.          * be initialized to be ``white'' (done elsewhere).
  271.          */
  272.         sp->refline = (u_char *)tif->tif_data + space + 1;
  273.         /*
  274.          * Initialize pixel just to the left of the
  275.          * reference line to white.  This extra pixel
  276.          * simplifies the edge-condition logic.
  277.          */
  278.         sp->refline[-1] = sp->white ? 0xff : 0x00;
  279.     } else
  280.         sp->refline = 0;
  281.     return (sp);
  282. }
  283.  
  284. /*
  285.  * Setup state for decoding a strip.
  286.  */
  287. static
  288. Fax3PreDecode(tif)
  289.     TIFF *tif;
  290. {
  291.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  292.  
  293.     if (sp == NULL) {
  294.         sp = (Fax3DecodeState *)Fax3SetupState(tif, sizeof (*sp));
  295.         if (!sp)
  296.             return (0);
  297.     }
  298.     sp->b.bit = 0;            /* force initial read */
  299.     sp->b.data = 0;
  300.     sp->b.tag = G3_1D;
  301.     if (sp->b.refline)
  302.         bset(sp->b.refline, sp->b.rowbytes, sp->b.white ? 0xff : 0x00);
  303.     /*
  304.      * If image has EOL codes, they precede each line
  305.      * of data.  We skip over the first one here so that
  306.      * when we decode rows, we can use an EOL to signal
  307.      * that less than the expected number of pixels are
  308.      * present for the scanline.
  309.      */
  310.     if ((tif->tif_options & FAX3_NOEOL) == 0) {
  311.         skiptoeol(tif, 0);
  312.         if (is2DEncoding(tif))
  313.             /* tag should always be 1D! */
  314.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  315.     }
  316.     return (1);
  317. }
  318.  
  319. /*
  320.  * Fill a span with ones.
  321.  */
  322. static void
  323. fillspan(cp, x, count)
  324.     register char *cp;
  325.     register int x, count;
  326. {
  327.     static const unsigned char masks[] =
  328.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  329.  
  330.     if (count <= 0)
  331.         return;
  332.     cp += x>>3;
  333.     if (x &= 7) {            /* align to byte boundary */
  334.         if (count < 8 - x) {
  335.             *cp++ |= masks[count] >> x;
  336.             return;
  337.         }
  338.         *cp++ |= 0xff >> x;
  339.         count -= 8 - x;
  340.     }
  341.     while (count >= 8) {
  342.         *cp++ = 0xff;
  343.         count -= 8;
  344.     }
  345.     *cp |= masks[count];
  346. }
  347.  
  348. /*
  349.  * Decode the requested amount of data.
  350.  */
  351. static
  352. Fax3Decode(tif, buf, occ, s)
  353.     TIFF *tif;
  354.     u_char *buf;
  355.     int occ;
  356.     u_int s;
  357. {
  358.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  359.  
  360.     bzero(buf, occ);        /* decoding only sets non-zero bits */
  361.     while (occ > 0) {
  362.         if (sp->b.tag == G3_1D) {
  363.             if (!Fax3Decode1DRow(tif, buf, sp->b.rowpixels))
  364.                 return (0);
  365.         } else {
  366.             if (!Fax3Decode2DRow(tif, buf, sp->b.rowpixels))
  367.                 return (0);
  368.         }
  369.         if (is2DEncoding(tif)) {
  370.             /*
  371.              * Fetch the tag bit that indicates
  372.              * whether the next row is 1d or 2d
  373.              * encoded.  If 2d-encoded, then setup
  374.              * the reference line from the decoded
  375.              * scanline just completed.
  376.              */
  377.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  378.             if (sp->b.tag == G3_2D)
  379.                 bcopy(buf, sp->b.refline, sp->b.rowbytes);
  380.         }
  381.         buf += sp->b.rowbytes;
  382.         occ -= sp->b.rowbytes;
  383.     }
  384.     return (1);
  385. }
  386.  
  387. /*
  388.  * Decode a run of white.
  389.  */
  390. static int
  391. decode_white_run(tif)
  392.     TIFF *tif;
  393. {
  394.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  395.     short state = sp->b.bit;
  396.     short action;
  397.     int runlen = 0;
  398.  
  399.     for (;;) {
  400.         if (sp->b.bit == 0) {
  401.     nextbyte:
  402.             if (tif->tif_rawcc <= 0)
  403.                 return (G3CODE_EOF);
  404.             sp->b.data = fetchByte(tif, sp);
  405.         }
  406.         action = TIFFFax1DAction[state][sp->b.data];
  407.         state = TIFFFax1DNextState[state][sp->b.data];
  408.         if (action == ACT_INCOMP)
  409.             goto nextbyte;
  410.         if (action == ACT_INVALID)
  411.             return (G3CODE_INVALID);
  412.         if (action == ACT_EOL)
  413.             return (G3CODE_EOL);
  414.         sp->b.bit = state;
  415.         action = RUNLENGTH(action - ACT_WRUNT);
  416.         runlen += action;
  417.         if (action < 64)
  418.             return (runlen);
  419.     }
  420.     /*NOTREACHED*/
  421. }
  422.  
  423. /*
  424.  * Decode a run of black.
  425.  */
  426. static int
  427. decode_black_run(tif)
  428.     TIFF *tif;
  429. {
  430.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  431.     short state = sp->b.bit + 8;
  432.     short action;
  433.     int runlen = 0;
  434.  
  435.     for (;;) {
  436.         if (sp->b.bit == 0) {
  437.     nextbyte:
  438.             if (tif->tif_rawcc <= 0)
  439.                 return (G3CODE_EOF);
  440.             sp->b.data = fetchByte(tif, sp);
  441.         }
  442.         action = TIFFFax1DAction[state][sp->b.data];
  443.         state = TIFFFax1DNextState[state][sp->b.data];
  444.         if (action == ACT_INCOMP)
  445.             goto nextbyte;
  446.         if (action == ACT_INVALID)
  447.             return (G3CODE_INVALID);
  448.         if (action == ACT_EOL)
  449.             return (G3CODE_EOL);
  450.         sp->b.bit = state;
  451.         action = RUNLENGTH(action - ACT_BRUNT);
  452.         runlen += action;
  453.         if (action < 64)
  454.             return (runlen);
  455.         state += 8;
  456.     }
  457.     /*NOTREACHED*/
  458. }
  459.  
  460. /*
  461.  * Process one row of 1d Huffman-encoded data.
  462.  */
  463. static int
  464. Fax3Decode1DRow(tif, buf, npels)
  465.     TIFF *tif;
  466.     u_char *buf;
  467.     int npels;
  468. {
  469.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  470.     int x = 0;
  471.     int runlen;
  472.     short action;
  473.     short color = sp->b.white;
  474.     static char module[] = "Fax3Decode1D";
  475.  
  476.     for (;;) {
  477.         if (color == sp->b.white)
  478.             runlen = decode_white_run(tif);
  479.         else
  480.             runlen = decode_black_run(tif);
  481.         switch (runlen) {
  482.         case G3CODE_EOF:
  483.             TIFFError(module,
  484.                 "%s: Premature EOF at scanline %d (x %d)",
  485.                 tif->tif_name, tif->tif_row, x);
  486.             return (0);
  487.         case G3CODE_INVALID:    /* invalid code */
  488.             /*
  489.              * An invalid code was encountered.
  490.              * Flush the remainder of the line
  491.              * and allow the caller to decide whether
  492.              * or not to continue.  Note that this
  493.              * only works if we have a G3 image
  494.              * with EOL markers.
  495.              */
  496.             TIFFError(module,
  497.                "%s: Bad code word at scanline %d (x %d)",
  498.                tif->tif_name, tif->tif_row, x);
  499.             goto done;
  500.         case G3CODE_EOL:    /* premature end-of-line code */
  501.             TIFFWarning(module,
  502.                 "%s: Premature EOL at scanline %d (x %d)",
  503.                 tif->tif_name, tif->tif_row, x);
  504.             return (1);    /* try to resynchronize... */
  505.         }
  506.         if (x+runlen > npels)
  507.             runlen = npels-x;
  508.         if (runlen > 0) {
  509.             if (color)
  510.                 fillspan((char *)buf, x, runlen);
  511.             x += runlen;
  512.             if (x >= npels)
  513.                 break;
  514.         }
  515.         color = !color;
  516.     }
  517. done:
  518.     /*
  519.      * Cleanup at the end of the row.  This convoluted
  520.      * logic is merely so that we can reuse the code with
  521.      * two other related compression algorithms (2 & 32771).
  522.      *
  523.      * Note also that our handling of word alignment assumes
  524.      * that the buffer is at least word aligned.  This is
  525.      * the case for most all versions of malloc (typically
  526.      * the buffer is returned longword aligned).
  527.      */
  528.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  529.         skiptoeol(tif, 0);
  530.     if (tif->tif_options & FAX3_BYTEALIGN)
  531.         sp->b.bit = 0;
  532.     if ((tif->tif_options & FAX3_WORDALIGN) && ((long)tif->tif_rawcp & 1))
  533.         (void) fetchByte(tif, sp);
  534.     return (x == npels);
  535. }
  536.  
  537. /*
  538.  * Group 3 2d Decoding support.
  539.  */
  540.  
  541. /*
  542.  * Return the next uncompressed mode code word.
  543.  */
  544. static int
  545. decode_uncomp_code(tif)
  546.     TIFF *tif;
  547. {
  548.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  549.     short code;
  550.  
  551.     do {
  552.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  553.             if (tif->tif_rawcc <= 0)
  554.                 return (UNCOMP_EOF);
  555.             sp->b.data = fetchByte(tif, sp);
  556.         }
  557.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  558.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  559.     } while (code == ACT_INCOMP);
  560.     return (code);
  561. }
  562.  
  563. /*
  564.  * Process one row of 2d encoded data.
  565.  */
  566. int
  567. Fax3Decode2DRow(tif, buf, npels)
  568.     TIFF *tif;
  569.     u_char *buf;
  570.     int npels;
  571. {
  572. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  573.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  574.     int a0 = -1;
  575.     int b1, b2;
  576.     int run1, run2;        /* for horizontal mode */
  577.     short mode;
  578.     short color = sp->b.white;
  579.     static char module[] = "Fax3Decode2D";
  580.  
  581.     do {
  582.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  583.             if (tif->tif_rawcc <= 0) {
  584.                 TIFFError(module,
  585.                 "%s: Premature EOF at scanline %d",
  586.                     tif->tif_name, tif->tif_row);
  587.                 return (0);
  588.             }
  589.             sp->b.data = fetchByte(tif, sp);
  590.         }
  591.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  592.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  593.         switch (mode) {
  594.         case MODE_NULL:
  595.             break;
  596.         case MODE_PASS:
  597.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  598.             b1 = finddiff(sp->b.refline, b2, npels, color);
  599.             b2 = finddiff(sp->b.refline, b1, npels, !color);
  600.             if (color) {
  601.                 if (a0 < 0)
  602.                     a0 = 0;
  603.                 fillspan((char *)buf, a0, b2 - a0);
  604.             }
  605.             a0 = b2;
  606.             break;
  607.         case MODE_HORIZ:
  608.             if (color == sp->b.white) {
  609.                 run1 = decode_white_run(tif);
  610.                 run2 = decode_black_run(tif);
  611.             } else {
  612.                 run1 = decode_black_run(tif);
  613.                 run2 = decode_white_run(tif);
  614.             }
  615.             /*
  616.              * Do the appropriate fill.  Note that we exit
  617.              * this logic with the same color that we enter
  618.              * with since we do 2 fills.  This explains the
  619.              * somewhat obscure logic below.
  620.              */
  621.             if (a0 < 0)
  622.                 a0 = 0;
  623.             if (a0 + run1 > npels)
  624.                 run1 = npels - a0;
  625.             if (color)
  626.                 fillspan((char *)buf, a0, run1);
  627.             a0 += run1;
  628.             if (a0 + run2 > npels)
  629.                 run2 = npels - a0;
  630.             if (!color)
  631.                 fillspan((char *)buf, a0, run2);
  632.             a0 += run2;
  633.             break;
  634.         case MODE_VERT_V0:
  635.         case MODE_VERT_VR1:
  636.         case MODE_VERT_VR2:
  637.         case MODE_VERT_VR3:
  638.         case MODE_VERT_VL1:
  639.         case MODE_VERT_VL2:
  640.         case MODE_VERT_VL3:
  641.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  642.             b1 = finddiff(sp->b.refline, b2, npels, color);
  643.             b1 += mode - MODE_VERT_V0;
  644.             if (color) {
  645.                 if (a0 < 0)
  646.                     a0 = 0;
  647.                 fillspan((char *)buf, a0, b1 - a0);
  648.             }
  649.             color = !color;
  650.             a0 = b1;
  651.             break;
  652.             case MODE_UNCOMP:
  653.             /*
  654.              * Uncompressed mode: select from the
  655.              * special set of code words.
  656.              */
  657.             if (a0 < 0)
  658.                 a0 = 0;
  659.             do {
  660.                 mode = decode_uncomp_code(tif);
  661.                 switch (mode) {
  662.                 case UNCOMP_RUN1:
  663.                 case UNCOMP_RUN2:
  664.                 case UNCOMP_RUN3:
  665.                 case UNCOMP_RUN4:
  666.                 case UNCOMP_RUN5:
  667.                     run1 = mode - UNCOMP_RUN0;
  668.                     fillspan((char *)buf, a0+run1-1, 1);
  669.                     a0 += run1;
  670.                     break;
  671.                 case UNCOMP_RUN6:
  672.                     a0 += 5;
  673.                     break;
  674.                 case UNCOMP_TRUN0:
  675.                 case UNCOMP_TRUN1:
  676.                 case UNCOMP_TRUN2:
  677.                 case UNCOMP_TRUN3:
  678.                 case UNCOMP_TRUN4:
  679.                     run1 = mode - UNCOMP_TRUN0;
  680.                     a0 += run1;
  681.                     color = nextbit(tif) ?
  682.                         !sp->b.white : sp->b.white;
  683.                     break;
  684.                 case UNCOMP_INVALID:
  685.                     TIFFError(module,
  686.                 "%s: Bad uncompressed code word at scanline %d",
  687.                         tif->tif_name, tif->tif_row);
  688.                     goto bad;
  689.                 case UNCOMP_EOF:
  690.                     TIFFError(module,
  691.                         "%s: Premature EOF at scanline %d",
  692.                         tif->tif_name, tif->tif_row);
  693.                     return (0);
  694.                 }
  695.             } while (mode < UNCOMP_EXIT);
  696.             break;
  697.             case MODE_ERROR_1:
  698.             if ((tif->tif_options & FAX3_NOEOL) == 0) {
  699.                 TIFFWarning(module,
  700.                     "%s: Premature EOL at scanline %d (x %d)",
  701.                     tif->tif_name, tif->tif_row, a0);
  702.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  703.                 return (1);        /* try to synchronize */
  704.             }
  705.             /* fall thru... */
  706.             case MODE_ERROR:
  707.             TIFFError(module,
  708.                 "%s: Bad 2D code word at scanline %d",
  709.                 tif->tif_name, tif->tif_row);
  710.             goto bad;
  711.             default:
  712.             TIFFError(module,
  713.                 "%s: Panic, bad decoding state at scanline %d",
  714.                 tif->tif_name, tif->tif_row);
  715.             return (0);
  716.         }
  717.     } while (a0 < npels);
  718. bad:
  719.     /*
  720.      * Cleanup at the end of row.  We check for
  721.      * EOL separately so that this code can be
  722.      * reused by the Group 4 decoding routine.
  723.      */
  724.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  725.         skiptoeol(tif, 0);
  726.     return (a0 >= npels);
  727. #undef    PIXEL
  728. }
  729.  
  730. /*
  731.  * CCITT Group 3 FAX Encoding.
  732.  */
  733.  
  734. /*
  735.  * Write a variable-length bit-value to
  736.  * the output stream.  Values are
  737.  * assumed to be at most 16 bits.
  738.  */
  739. static void
  740. putbits(tif, bits, length)
  741.     TIFF *tif;
  742.     u_int bits, length;
  743. {
  744.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  745.     static const int mask[9] =
  746.         { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  747.  
  748.     while (length > sp->bit) {
  749.         sp->data |= bits >> (length - sp->bit);
  750.         length -= sp->bit;
  751.         Fax3FlushBits(tif, sp);
  752.     }
  753.     sp->data |= (bits & mask[length]) << (sp->bit - length);
  754.     sp->bit -= length;
  755.     if (sp->bit == 0)
  756.         Fax3FlushBits(tif, sp);
  757. }
  758.  
  759. /*
  760.  * Write a code to the output stream.
  761.  */
  762. static void
  763. putcode(tif, te)
  764.     TIFF *tif;
  765.     tableentry const *te;
  766. {
  767.     putbits(tif, te->code, te->length);
  768. }
  769.  
  770. /*
  771.  * Write the sequence of codes that describes
  772.  * the specified span of zero's or one's.  The
  773.  * appropriate table that holds the make-up and
  774.  * terminating codes is supplied.
  775.  */
  776. static void
  777. putspan(tif, span, tab)
  778.     TIFF *tif;
  779.     int span;
  780.     tableentry const *tab;
  781. {
  782.     while (span >= 2624) {
  783.         tableentry const *te = &tab[63 + (2560>>6)];
  784.         putcode(tif, te);
  785.         span -= te->runlen;
  786.     }
  787.     if (span >= 64) {
  788.         tableentry const *te = &tab[63 + (span>>6)];
  789.         assert(te->runlen == 64*(span>>6));
  790.         putcode(tif, te);
  791.         span -= te->runlen;
  792.     }
  793.     putcode(tif, &tab[span]);
  794. }
  795.  
  796. /*
  797.  * Write an EOL code to the output stream.  The zero-fill
  798.  * logic for byte-aligning encoded scanlines is handled
  799.  * here.  We also handle writing the tag bit for the next
  800.  * scanline when doing 2d encoding.
  801.  */
  802. void
  803. Fax3PutEOL(tif)
  804.     TIFF *tif;
  805. {
  806.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  807.  
  808.     if (tif->tif_dir.td_group3options & GROUP3OPT_FILLBITS) {
  809.         /*
  810.          * Force bit alignment so EOL will terminate on
  811.          * a byte boundary.  That is, force the bit alignment
  812.          * to 16-12 = 4 before putting out the EOL code.
  813.          */
  814.         int align = 8 - 4;
  815.         if (align != sp->bit) {
  816.             if (align > sp->bit)
  817.                 align = sp->bit + (8 - align);
  818.             else
  819.                 align = sp->bit - align;
  820.             putbits(tif, 0, align);
  821.         }
  822.     }
  823.     putbits(tif, EOL, 12);
  824.     if (is2DEncoding(tif))
  825.         putbits(tif, sp->tag == G3_1D, 1);
  826. }
  827.  
  828. static const u_char zeroruns[256] = {
  829.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  830.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  831.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  832.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  833.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  834.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  835.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  836.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  837.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  838.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  839.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  840.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  841.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  842.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  843.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  844.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  845. };
  846. static const u_char oneruns[256] = {
  847.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  848.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  849.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  850.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  851.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  852.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  853.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  854.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  855.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  856.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  857.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  858.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  859.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  860.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  861.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  862.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  863. };
  864.  
  865. /*
  866.  * Reset encoding state at the start of a strip.
  867.  */
  868. static
  869. Fax3PreEncode(tif)
  870.     TIFF *tif;
  871. {
  872.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  873.  
  874.     if (sp == NULL) {
  875.         sp = (Fax3EncodeState *)Fax3SetupState(tif, sizeof (*sp));
  876.         if (!sp)
  877.             return (0);
  878.         if (sp->b.white == 0) {
  879.             sp->wruns = zeroruns;
  880.             sp->bruns = oneruns;
  881.         } else {
  882.             sp->wruns = oneruns;
  883.             sp->bruns = zeroruns;
  884.         }
  885.     }
  886.     sp->b.bit = 8;
  887.     sp->b.data = 0;
  888.     sp->b.tag = G3_1D;
  889.     /*
  890.      * This is necessary for Group 4; otherwise it isn't
  891.      * needed because the first scanline of each strip ends
  892.      * up being copied into the refline.
  893.      */
  894.     if (sp->b.refline)
  895.         bset(sp->b.refline, sp->b.rowbytes, sp->b.white ? 0xff : 0x00);
  896.     if (is2DEncoding(tif)) {
  897.         float res = tif->tif_dir.td_yresolution;
  898.         /*
  899.          * The CCITT spec says that when doing 2d encoding, you
  900.          * should only do it on K consecutive scanlines, where K
  901.          * depends on the resolution of the image being encoded
  902.          * (2 for <= 200 lpi, 4 for > 200 lpi).  Since the directory
  903.          * code initializes td_yresolution to 0, this code will
  904.          * select a K of 2 unless the YResolution tag is set
  905.          * appropriately.  (Note also that we fudge a little here
  906.          * and use 150 lpi to avoid problems with units conversion.)
  907.          */
  908.         if (tif->tif_dir.td_resolutionunit == RESUNIT_CENTIMETER)
  909.             res = (res * .3937) / 2.54;    /* convert to inches */
  910.         sp->maxk = (res > 150 ? 4 : 2);
  911.         sp->k = sp->maxk-1;
  912.     } else
  913.         sp->k = sp->maxk = 0;
  914.     return (1);
  915. }
  916.  
  917. /*
  918.  * 1d-encode a row of pixels.  The encoding is
  919.  * a sequence of all-white or all-black spans
  920.  * of pixels encoded with Huffman codes.
  921.  */
  922. static int
  923. Fax3Encode1DRow(tif, bp, bits)
  924.     TIFF *tif;
  925.     u_char *bp;
  926.     int bits;
  927. {
  928.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  929.     int bs = 0, span;
  930.  
  931.     for (;;) {
  932.         span = findspan(&bp, bs, bits, sp->wruns);    /* white span */
  933.         putspan(tif, span, TIFFFaxWhiteCodes);
  934.         bs += span;
  935.         if (bs >= bits)
  936.             break;
  937.         span = findspan(&bp, bs, bits, sp->bruns);    /* black span */
  938.         putspan(tif, span, TIFFFaxBlackCodes);
  939.         bs += span;
  940.         if (bs >= bits)
  941.             break;
  942.     }
  943.     return (1);
  944. }
  945.  
  946. static const tableentry horizcode =
  947.     { 3, 0x1 };        /* 001 */
  948. static const tableentry passcode =
  949.     { 4, 0x1 };        /* 0001 */
  950. static const tableentry vcodes[7] = {
  951.     { 7, 0x03 },    /* 0000 011 */
  952.     { 6, 0x03 },    /* 0000 11 */
  953.     { 3, 0x03 },    /* 011 */
  954.     { 1, 0x1 },        /* 1 */
  955.     { 3, 0x2 },        /* 010 */
  956.     { 6, 0x02 },    /* 0000 10 */
  957.     { 7, 0x02 }        /* 0000 010 */
  958. };
  959.  
  960. /*
  961.  * 2d-encode a row of pixels.  Consult the CCITT
  962.  * documentation for the algorithm.
  963.  */
  964. int
  965. Fax3Encode2DRow(tif, bp, rp, bits)
  966.     TIFF *tif;
  967.     u_char *bp, *rp;
  968.     int bits;
  969. {
  970. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  971.     short white = ((Fax3BaseState *)tif->tif_data)->white;
  972.     int a0 = 0;
  973.     int a1 = (PIXEL(bp, 0) != white ? 0 : finddiff(bp, 0, bits, white));
  974.     int b1 = (PIXEL(rp, 0) != white ? 0 : finddiff(rp, 0, bits, white));
  975.     int a2, b2;
  976.  
  977.     for (;;) {
  978.         b2 = finddiff(rp, b1, bits, PIXEL(rp,b1));
  979.         if (b2 >= a1) {
  980.             int d = b1 - a1;
  981.             if (!(-3 <= d && d <= 3)) {    /* horizontal mode */
  982.                 a2 = finddiff(bp, a1, bits, PIXEL(bp,a1));
  983.                 putcode(tif, &horizcode);
  984.                 if (a0+a1 == 0 || PIXEL(bp, a0) == white) {
  985.                     putspan(tif, a1-a0, TIFFFaxWhiteCodes);
  986.                     putspan(tif, a2-a1, TIFFFaxBlackCodes);
  987.                 } else {
  988.                     putspan(tif, a1-a0, TIFFFaxBlackCodes);
  989.                     putspan(tif, a2-a1, TIFFFaxWhiteCodes);
  990.                 }
  991.                 a0 = a2;
  992.             } else {            /* vertical mode */
  993.                 putcode(tif, &vcodes[d+3]);
  994.                 a0 = a1;
  995.             }
  996.         } else {                /* pass mode */
  997.             putcode(tif, &passcode);
  998.             a0 = b2;
  999.         }
  1000.         if (a0 >= bits)
  1001.             break;
  1002.         a1 = finddiff(bp, a0, bits, PIXEL(bp,a0));
  1003.         b1 = finddiff(rp, a0, bits, !PIXEL(bp,a0));
  1004.         b1 = finddiff(rp, b1, bits, PIXEL(bp,a0));
  1005.     }
  1006.     return (1);
  1007. #undef PIXEL
  1008. }
  1009.  
  1010. /*
  1011.  * Encode a buffer of pixels.
  1012.  */
  1013. static int
  1014. Fax3Encode(tif, bp, cc, s)
  1015.     TIFF *tif;
  1016.     u_char *bp;
  1017.     int cc;
  1018.     u_int s;
  1019. {
  1020.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  1021.  
  1022.     while (cc > 0) {
  1023.         Fax3PutEOL(tif);
  1024.         if (is2DEncoding(tif)) {
  1025.             if (sp->b.tag == G3_1D) {
  1026.                 if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  1027.                     return (0);
  1028.                 sp->b.tag = G3_2D;
  1029.             } else {
  1030.                 if (!Fax3Encode2DRow(tif, bp, sp->b.refline, sp->b.rowpixels))
  1031.                     return (0);
  1032.                 sp->k--;
  1033.             }
  1034.             if (sp->k == 0) {
  1035.                 sp->b.tag = G3_1D;
  1036.                 sp->k = sp->maxk-1;
  1037.             } else
  1038.                 bcopy(bp, sp->b.refline, sp->b.rowbytes);
  1039.         } else {
  1040.             if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  1041.                 return (0);
  1042.         }
  1043.         bp += sp->b.rowbytes;
  1044.         cc -= sp->b.rowbytes;
  1045.     }
  1046.     return (1);
  1047. }
  1048.  
  1049. static int
  1050. Fax3PostEncode(tif)
  1051.     TIFF *tif;
  1052. {
  1053.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  1054.  
  1055.     if (sp->bit != 8)
  1056.         Fax3FlushBits(tif, sp);
  1057.     return (1);
  1058. }
  1059.  
  1060. static
  1061. Fax3Close(tif)
  1062.     TIFF *tif;
  1063. {
  1064.     if ((tif->tif_options & FAX3_CLASSF) == 0) {    /* append RTC */
  1065.         int i;
  1066.         for (i = 0; i < 6; i++)
  1067.             Fax3PutEOL(tif);
  1068.         (void) Fax3PostEncode(tif);
  1069.     }
  1070. }
  1071.  
  1072. static
  1073. Fax3Cleanup(tif)
  1074.     TIFF *tif;
  1075. {
  1076.     if (tif->tif_data) {
  1077.         free(tif->tif_data);
  1078.         tif->tif_data = NULL;
  1079.     }
  1080. }
  1081.  
  1082. /*
  1083.  * Bit handling utilities.
  1084.  */
  1085.  
  1086. /*
  1087.  * Find a span of ones or zeros using the supplied
  1088.  * table.  The byte-aligned start of the bit string
  1089.  * is supplied along with the start+end bit indices.
  1090.  * The table gives the number of consecutive ones or
  1091.  * zeros starting from the msb and is indexed by byte
  1092.  * value.
  1093.  */
  1094. static int
  1095. findspan(bpp, bs, be, tab)
  1096.     u_char **bpp;
  1097.     int bs, be;
  1098.     register u_char const *tab;
  1099. {
  1100.     register u_char *bp = *bpp;
  1101.     register int bits = be - bs;
  1102.     register int n, span;
  1103.  
  1104.     /*
  1105.      * Check partial byte on lhs.
  1106.      */
  1107.     if (bits > 0 && (n = (bs & 7))) {
  1108.         span = tab[(*bp << n) & 0xff];
  1109.         if (span > 8-n)        /* table value too generous */
  1110.             span = 8-n;
  1111.         if (span > bits)    /* constrain span to bit range */
  1112.             span = bits;
  1113.         if (n+span < 8)        /* doesn't extend to edge of byte */
  1114.             goto done;
  1115.         bits -= span;
  1116.         bp++;
  1117.     } else
  1118.         span = 0;
  1119.     /*
  1120.      * Scan full bytes for all 1's or all 0's.
  1121.      */
  1122.     while (bits >= 8) {
  1123.         n = tab[*bp];
  1124.         span += n;
  1125.         bits -= n;
  1126.         if (n < 8)        /* end of run */
  1127.             goto done;
  1128.         bp++;
  1129.     }
  1130.     /*
  1131.      * Check partial byte on rhs.
  1132.      */
  1133.     if (bits > 0) {
  1134.         n = tab[*bp];
  1135.         span += (n > bits ? bits : n);
  1136.     }
  1137. done:
  1138.     *bpp = bp;
  1139.     return (span);
  1140. }
  1141.  
  1142. /*
  1143.  * Return the offset of the next bit in the range
  1144.  * [bs..be] that is different from the specified
  1145.  * color.  The end, be, is returned if no such bit
  1146.  * exists.
  1147.  */
  1148. static int
  1149. finddiff(cp, bs, be, color)
  1150.     u_char *cp;
  1151.     int bs, be, color;
  1152. {
  1153.     cp += bs >> 3;            /* adjust byte offset */
  1154.     return (bs + findspan(&cp, bs, be, color ? oneruns : zeroruns));
  1155. }
  1156.